#include <stdio.h>
#include<stdlib.h>
int IsInsertion(int* A, int* B, int N);/*判断是否插人排序*/
void PrintResults(int* B, int N);/*输出结果序列*/
void NextInsertion(int* B, int N, int K);/*执行下一步插人*/
int MergeLength(int* B, int N);/*找出归并段长度*/
void NextMerge(int* B, int N);/*执行下一步归并*/
int main() {
    int N, i, k;
    int * A, * B;
    scanf("%d",&N);
    //A,B动态分布空间
    A = (int*)malloc(sizeof(int) * N);
    B = (int*)malloc(sizeof(int) * N);
    for (i = 0; i < N; i++)//存原始序列
        scanf("%d", &A[i]);
    for (i = 0; i < N; i++)//存中间序列
        scanf("%d", &B[i]);
    if (k = IsInsertion(A, B, N))//如果是插入排序
        NextInsertion(B, N, k);//执行下一步插入
    else
        NextMerge(B, N);//执行下一步归并

}
int IsInsertion(int* A, int* B, int N)//判断是否为插入排序
{
    int i, k;
    for (i = 1; i < N; i++){
         if (B[i] < B[i - 1])
            break;//发现顺序不对
    }  
    k = i;//可能是插人排序的有序序列尾部位置
    for(;i<N;i++){
        if(B[i]!=A[i]) 
            break;/*发现后面序列有变化*/
    }
    if(i==N)
        return k;/*是插入排序，返回插入位置*/
    else
        return 0;/*不是插入排序*/
}
void PrintResults(int* B, int N) {
    int i;
    printf("%d", B[0]);
    for (i = 1; i < N; i++)printf(" %d", B[i]);
    printf("\n");
}
void NextInsertion(int* B, int N, int K) {

    int i, tmp;
    printf("Insertion Sort\n");
    tmp = B[K];
    for (i = K - 1; i >= 0; i--){
        if (tmp < B[i])
            B[i + 1] = B[i];
        else
            break;
    }   
    B[i + 1] = tmp;
    PrintResults(B, N);
}
int MergeLength(int* B, int N) {
    int i, l;
    for (l = 2; 1 <= N; l *= 2) {
        for (i = l; i < N; i += (l + l))
            if (B[i - 1] > B[i])break;
        if (i < N)break;
    }
    return l;
}
void NextMerge(int* B, int N) {
    int i, p1, p2, p, L;
    int* Tmp;
    Tmp = (int*)malloc(sizeof(int) * N);
    printf("Merge Sort\n");
    /*找出当前归并段长度*/
    L = MergeLength(B, N);
    /*开始归并*/
    p= 0;/*p指向Tmp中当前处理的位置*/
    for (i = 0; i < (N - L - L); i += (L + L)) { /*两两归并长度为L的段*/
        p1 = i;
        p2 = i + L;/*p1和 p2分别指向两个段的当前处理位置*/
        while ((p1 < (i + L)) && (p2 < (i + L + L))) {
            if (B[p1] > B[p2])Tmp[p++] = B[p2++];
            else Tmp[p++] = B[p1++];
        }
        while (p1 < (i + L))
            Tmp[p++] = B[p1++];
        while (p2 < (i + L + L))
            Tmp[p++] = B[p2++];
    }
    if ((N - i) > L) {/*如果最后剩2段，执行归并*/
        p1 = i; p2 = i + L;
        while ((p1 < (i + L)) && (p2 < N)) {
            if (B[p1] > B[p2])
                Tmp[p++] = B[p2++];
            else
                Tmp[p++] = B[p1++];
        }
        while (p1 < (i + L))
            Tmp[p++] = B[p1++];
        while (p2 < N)Tmp[p++] = B[p2++];
    }
    else /*最后只剩1段*/
        while (i < N)Tmp[i] = B[i++];
    PrintResults(Tmp, N);
}
